Batch 3 - Class 246 - State Diagrams and Turing Machines 1
(zoom)
Pre-Class Exercise
- (536Dudeney - 290) The outside wheels of a car, running on a circular track, are going twice as fast as the inside ones. What is the diameter of the circle traced by outer wheels? The wheels are five feet apart on the two axles.
- (Answer) 20 feet.
Attendance Kabir, Vansh, Kushagra, Rehaan, Vivaan, Advay, Mihir, Aneesh, Aarkin, Ayush, Arjun, Shikher, Harsheit, Anishka, Rohan.
Class Notes:
Ask kids to explain how they accomplish a simple activity, like getting up in the morning and getting ready - right from the alarm, to brushing their teeth, to taking a bath, and so on
- Is there the same routine on all days, or is it different sometimes - when is it different
- Uncover elements of procedures, triggers, and states
- How would the kids instruct a robot to "get up in the morning and get ready". How would they provide precise instructions?
- Lets think about playing a game, lets say tic tac toe. If you walked into a game of tic tac toe midway through, what all do you need to know to play the next turn? Do you need to know the full history?
- What does the current state of the board represent - everything that has happened in the past that is currently relevant.
- If you knew "style of a player" and that was relevant, that would be part of "state", like where does a batsman tend to hit in a game of cricket
Explain the notion of state diagram
- Has a notion of states as described above
- There may be several inputs/actions that happen when in a state
- On each of those inputs, the state changes (and well, there might be an output)
- Lets draw the state diagram of lifecycle of a chicken
- Let kids come up with a simple state machine, and draw it. Each student must think about one example and draw the state machine.
- Introduce notion of FSM - just that the number of states is finite. So a machine that can count infinitely is not a FSM.
- Every state must have an output and transition for every input.
Programming a Finite State Machine
- Discuss the programming of FSM through rules (if-then-else) statements. Need to store the state in a given variable.
- Discuss alternate programming style by storing the entire state machine in a table, and looking it up, depending on current state and input.
- This program could potentially solve any problem which can be modeled as a FSM, just by changing the table
- What set of programming instructions are required to be able to program any given state machine?
- Assignment, Conditional, Branch or Loop
- Note: Theoretically, there are single instruction computers possible. Example "Subtract and branch if less than or equal to zero" where three instruction addresses are passed, and vaue at address b is replaced by b-a, and if the result is not positive, the control is transferred to c. https://en.wikipedia.org/wiki/One-instruction_set_computer
Turing Machines
- Ask kids if they know what Turing machines are
- Why - how do we know which problems are solvable or not? Does it depend on the computer we use? Does it depend on the power of the computer? Does it depend on the programming language?
- Introduce a notion of a theoretical computer. Simple, standardized, and useful as a theoretical construct to analyze programs rather than to use physically.
References: